package leetcode_900;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

/**
 *@author 周杨
 *MaximumFrequencyStack_895 实现频率栈
 *describe:用map和栈实现 AC 25%
 *2018年11月12日 下午3:26:39
 */
public class MaximumFrequencyStack_895 {
	private final Map<Integer,Integer> valueCount=new HashMap<Integer,Integer>();
	private final TreeMap<Integer,Stack<Integer>> stackMap= new TreeMap<Integer,Stack<Integer>>();
	public void push(int x) {
		int count=valueCount.getOrDefault(x, 0)+1;//把key和count放入
		valueCount.put(x, count);
		stackMap.computeIfAbsent(count, a->new Stack<Integer>()).push(x);
		//因为stackMap是排序的 那么把原来的count放入
	}
	public int pop() {
		Stack<Integer> stack=stackMap.lastEntry().getValue();//返回最大的那个
		int x=stack.pop();
		if(stack.isEmpty())
			stackMap.remove(stackMap.lastKey());//删除这个栈
		valueCount.put(x, valueCount.get(x)-1);//减1
		return x;//因为关于x 的后面的次数 也在Tree里
	}
}
